#!/usr/bin/env python3

class Solution:
    def search(self, nums, target):
        if len(nums) == 0:
            return -1
        if nums[0] == target:
            return 0
        if nums[len(nums) - 1] == target:
            return len(nums) - 1
        return self._search(nums, target, 0, len(nums))

    def _search(self, nums, target, start, end):
        if end - 1 < start:
            return -1
        elif end - 1 == start:
            return start if nums[start] == target else -1
        start_val = nums[start]
        end_val = nums[end - 1]
        middle = int((start + end)/2)
        middle_val = nums[middle]
        if middle_val == target:
            return middle
        if end_val > start_val:
            # sorted array slice
            if start_val > target or target > end_val:
                return -1
            elif middle_val > target:
                return self._search(nums, target, start, middle)
            else:
                return self._search(nums, target, middle, end)
        else:
            # a rotated array
            result = self._search(nums, target, start, middle)
            if result == -1:
                result = self._search(nums, target, middle, end)
            return result

if __name__ == '__main__':
    solution = Solution()
    assert 4 == solution.search([4, 5, 6, 7, 0, 1, 2], 0)
    assert -1 == solution.search([4, 5, 6, 7, 0, 1, 2], 3)
